//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 
// 👍 797 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Java：柱状图中最大的矩形
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new P84_LargestRectangleInHistogram().new Solution();
        int[] nums = MyUtil.createArray(2, 1, 5, 6, 2, 3, 90, 100, 68);
        int area = solution.largestRectangleArea(nums);
        MyUtil.print(area);
    }

//    leetcode submit region begin(Prohibit modification and deletion)
//    /**
//     * 暴力求解, 枚举宽
//     * 时间复杂度 O(n^2)
//     */
//    class Solution {
//        public int largestRectangleArea(int[] heights) {
//            int area = 0;
//            for (int i = 0; i < heights.length; i++) {
//                // 最短
//                int min = heights[i];
//                for (int j = i; j < heights.length; j++) {
//                    min = Math.min(min, heights[j]);
//                    area = Math.max(area, (j - i + 1) * min);
//                }
//            }
//            return area;
//        }
//    }

//    /**
//     * 暴力求解, 固定高度找宽度
//     * 时间复杂度 O(n^2)
//     */
//    class Solution {
//        public int largestRectangleArea(int[] heights) {
//            int area = 0, j, k;
//            for (int i = 0; i < heights.length; i++) {
//                j = k = i;
//                while (j >= 0 && heights[j] >= heights[i]) {
//                    j--;
//                }
//                while (k < heights.length && heights[k] >= heights[i]) {
//                    k++;
//                }
//                area = Math.max(area, (k - j - 1) * heights[i]);
//            }
//            return area;
//        }
//    }

    /**
     * 单调栈
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    class Solution {
        public int largestRectangleArea(int[] heights) {
            if (heights.length == 0) {
                return 0;
            }
            if (heights.length == 1) {
                return heights[0];
            }

            int area = 0;
            // 增加前后哨兵
            int[] newHeights = new int[2 + heights.length];
            newHeights[0] = newHeights[newHeights.length - 1] = 0;
            System.arraycopy(heights, 0, newHeights, 1, heights.length);

            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < newHeights.length; i++) {
                if (stack.isEmpty()) {
                    stack.push(i);
                    continue;
                }

                while (newHeights[stack.peek()] > newHeights[i]) {
                    int curHeight = newHeights[stack.pop()];
                    int curWidth = i - stack.peek() - 1;
                    area = Math.max(area, curHeight * curWidth);
                }
                stack.push(i);
            }
            return area;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
//
}
